COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "memo.pub[let,jmc]" source_file
C00014 ENDMK
C⊗;
.require "memo.pub[let,jmc]" source_file;
.TURN OFF "{}∂[]"
.cb	CS206	Recursive Programming and Proving	   Fall 1980
.cb	Midterm Examination
.cb	Nov 14 1980
.skip 2

Write the following programs using either Maclisp or external notation.

You may use any books or notes that you wish on this test.

.SKIP 2
#.a. %2least[u]%1 is the least integer in the list %2u%1 of integers.

b. %2least1[x]%1 is the least integer in the s-expression %2x%1, all of whose
atoms are assumed to be integers.

#. a. %2flip2 u%1 reverses each pair of successive elements of ⊗u
starting with the first.  Thus

	%2flip2 %1(A B C D) = (B A D C)

and

	%2flip2 %1(A B C D E) = (B A D C E).

b. Prove that %2∀u.[flip2 flip2 u = u]%1.

#. a. Defining

	%2nth[u,n] ← qif n equal 1 qthen qa u qelse nth[qd u, n-1]%1

and

	%2index[u,x] ← qif x equal qa u qteen 1 qelse 1 + index[qd u, x]%1,

prove

	%2∀x u.[member[x,u] ⊃ nth[u,index[u,x]] = x]%1.

b. What additional conditions are require to prove

	%2index[u, nth[u, k]] = k%1?

Don't give the proof.

#. Assume that ⊗u is a list of lists of equal length representing
a matrix listed by rows.  %2transpose u%1 represents the transpose
of the matrix.  Thus

	%2transpose %1((A B C) (D E F)) = ((A D) (B E) (C F)).


#. The Linus sequence Linus(i) is an infinite sequence of 1's and 0's defined
as follows:

	Linus(1) = 1 
	Linus(i) = the number which breaks the longest "pattern" which
		   is threatening to occur,

where a "pattern" is defined to be two consecutive occurrences of the same
string of 1's and 0's. The length of a pattern is defined to be the length
of one of its halves. For instance,

	Length  Pattern
	------  -------
	1       0 0
	1       1 1
	2       1 0 1 0         
	3       1 0 1 1 0 1
	4       1 1 0 1 1 1 0 1

The first 12 terms of the Linus sequence are:

	1 0 1 1 0 0 1 0 1 1 0 1

Linus(2)=0 since otherwise we create the length 1 pattern "1 1". Clearly
the next term in the Linus sequence is always forced, since we can always
break a pattern of at least length 1. Linus(4) avoids the pattern "1 0 1 0".
Linus(12) creates the pattern "1 0 1 1 0 1", but avoids the longer pattern
"1 0 1 1 0 0 1 0 1 1 0 0".

Problem. Write the function LINUS[u] which appends the next term in the Linus
sequence to the beginning of u, where u is a list of the form

	[Linus(n), Linus(n-1), Linus(n-2)... Linus(2), Linus(1)]